/*
 * @Author: liusheng
 * @Date: 2022-06-01 18:40:47
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-01 18:44:07
 * @Description: 剑指 Offer II 067. 最大的异或
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 067. 最大的异或
给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

 

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：

输入：nums = [0]
输出：0
示例 3：

输入：nums = [2,4]
输出：6
示例 4：

输入：nums = [8,10,2]
输出：10
示例 5：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127
 

提示：

1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1
 

进阶：你可以在 O(n) 的时间解决这个问题吗？

 

注意：本题与主站 421 题相同： https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
 */

#include "header.h"

/*
Solution with Trie
*/
class Solution {
    class Trie
    {
        const  int HIGH_BIT = 30;
        //children[0] represent 0(left),children[1] represent 1(right)
        array<Trie *,2> children;
public:
        void insert(int num)
        {
            Trie * node = this;
            for (int i = HIGH_BIT; i >= 0; --i)
            {
                int curBit = (num >> i) & 1;
                if (!node->children[curBit])
                {
                    node->children[curBit] = new Trie();
                }
                node = node->children[curBit];
            }
        }

        int getSum(int num)
        {
            Trie * node = this;
            int sum = 0;
            for (int i = HIGH_BIT; i >= 0; --i)
            {
                int curBit = (num >> i) & 1;
                //另一分支非空,则将对应的异或结果累加
                if (node->children[curBit ^ 1] != nullptr)
                {
                    sum += (1 << i);
                    node = node->children[curBit ^ 1];
                }
                //另一分支为空,只能从当前分支前行
                else
                {
                    node = node->children[curBit];
                }
            }

            return sum;
        }
    };

    
public:
    int findMaximumXOR(vector<int>& nums) {
        Trie * root = new Trie();
        for (int num : nums)
        {
            root->insert(num);
        }

        int maxXor = 0;
        for (int num : nums)
        {
            maxXor = max(maxXor,root->getSum(num));
        }

        return maxXor;
    }
};